📚 数据库系统核心课程讲义 (Lecture 11-14)#

1. 核心概念解释#

• 为什么要排序？
  • 关系模型本身是无序的，但在以下情况数据库需要排序：
    • 查询显式要求 ORDER BY。
    • 为其他算法做准备（例如：构建 B+ 树索引、消除重复值 DISTINCT、Sort-Merge Join）。
• 内存不足时的策略
  • 如果数据能完全放入内存，使用标准的快速排序（Quicksort）等算法即可。
  • 核心挑战：当数据量超过缓冲池（Buffer Pool）大小时，必须使用**外部排序（External Sorting）**算法，目的是最大化顺序 I/O (Sequential I/O)。

2. 关键结论 / 公式 / 方法#

• Top-N Heap Sort (针对 ORDER BY ... LIMIT N)
  • 方法：不需要对全表排序。维护一个大小为 N 的内存堆（Priority Queue）。扫描数据时，如果新数据比堆顶元素更符合条件，则替换并调整堆。
  • 适用场景：查询只需返回少量顶部数据。
• External Merge Sort (外部归并排序)
  • 分治思想：将数据切分为能够放入内存的小块（Runs），分别排序后写回磁盘，再分阶段合并。
  • 算法流程：
    1. Pass 0 (Sorting Phase)：读取 $B$ 页数据，排序，写入磁盘作为 Run。
    2. Pass 1…N (Merge Phase)：使用 $B-1$ 个缓冲区读取输入 Runs，1 个缓冲区写输出。递归合并直到只剩一个 Run。
  • 成本公式：
    • 总 Passes 数 = $1 + \lceil \log_{B-1} \lceil N/B \rceil \rceil$ ($N$为总页数，$B$为缓冲页数)。
    • 总 I/O = $2N \times (\text{Passes数})$。
• 聚合算法 (Aggregations)
  • Sorting Aggregation：先排序，然后顺序扫描，相同的 Key 会聚集在一起，易于计算 Count/Sum/Avg。
  • Hashing Aggregation：建立临时哈希表。扫描数据，计算 Hash 值放入对应桶中更新聚合结果。通常比排序法更好，除非数据已经有序。

3. 易混点或易错点提示#

• ⚠️ Double Buffering (双缓冲)：为了防止 CPU 在等待磁盘 I/O 时闲置，可以使用额外的线程预取数据（Prefetching），但这需要占用一部分缓冲池内存。
• ⚠️ Early vs. Late Materialization：
  • Early (行存常用)：排序时携带整行数据（Key + Tuple）。优点是无需回表，缺点是占用带宽大。
  • Late (列存常用)：排序时只携带 Record ID (Key + RID)。优点是数据量小，缺点是最后需要随机 I/O 回表获取完整数据。

4. 简短复习小结#

排序是数据库的基础操作。当内存充足时用快排；内存不足时用外部归并排序（利用分治和顺序 I/O）。聚合操作通常首选哈希法，除非数据已有序。

1. 核心概念解释#

• 连接的目标：将两个表（R 和 S）中满足特定条件（通常是等值连接 Equi-Join）的元组组合在一起。
• 设计原则：
  • 通常将较小的表作为“外表”（Outer Table），较大的表作为“内表”（Inner Table）。
  • 目标是最小化磁盘 I/O，而不是仅计算比较次数。

2. 关键结论 / 公式 / 方法#

• Nested Loop Join (NLJ)
  • Naive NLJ：傻瓜式双重循环。对 R 中每一行，扫描 S 全表。极慢，不可用。
  • Block NLJ：按“块”（Page）进行循环。读入一块 R，扫描一遍 S。利用了缓冲池，性能大幅提升。
  • Index NLJ：如果内表 S 在连接键上有索引，直接查索引而非扫全表。
• Sort-Merge Join (SMJ)
  • 方法：先对 R 和 S 进行排序（Phase 1），然后使用游标同步扫描合并（Phase 2）。
  • 回溯 (Backtracking)：如果连接键有重复值，归并时游标可能需要回退。
  • 适用场景：数据已经有序，或输出结果要求有序。
• Hash Join (最重要的算法)
  • Simple Hash Join：内存够大时，对小表 R 建哈希表，扫描大表 S 进行探测（Probe）。
  • Grace Hash Join (Partitioned Hash Join)：
    • Phase 1 (Partition)：对 R 和 S 使用相同的 Hash 函数 $h1$ 切分到不同的磁盘桶中。
    • Phase 2 (Probe)：对每一对对应的桶，加载到内存构建小哈希表并连接。
  • Bloom Filter 优化：在构建哈希表时创建一个 Bloom Filter，探测阶段先查 Bloom Filter，若不存在则直接跳过，减少哈希表查找开销。

3. 易混点或易错点提示#

• ⚠️ Hash Join 退化：如果所有 Key 都 Hash 到同一个桶（数据倾斜），Grace Hash Join 会失效，此时需回退到 Block Nested Loop Join。
• ⚠️ 代价估算：Nested Loop 适合小表或有索引；Hash Join 适合大表且无序；Sort-Merge 适合已有序数据。但在现代系统中，Hash Join 几乎总是优于 Sort-Merge Join。

4. 简短复习小结#

连接是数据库最昂贵的操作之一。Block Nested Loop 是保底方案；Index Nested Loop 利用现有索引最快；对于大数据量的全表连接，Hash Join（特别是带 Bloom Filter）通常是性能之王。

1. 核心概念解释#

• 处理模型 (Processing Models)：定义系统如何执行查询计划（Plan）并在算子（Operators）间传递数据。
• 访问方法 (Access Methods)：从磁盘读取数据的方式（全表扫描 vs 索引扫描）。

2. 关键结论 / 公式 / 方法#

• 三种处理模型：
  1. Iterator Model (Volcano Model)：
     • 每个算子实现 next()。父节点调用子节点的 next() 获取一行数据。
     • 优点：简单，内存占用小（Pipelining）。缺点：函数调用开销大。
     • 适用：OLTP 系统 (MySQL, Postgres)。
  2. Materialization Model：
     • 每个算子一次性处理所有输入，将结果物化（存下来）返回给父节点。
     • 优点：减少函数调用。缺点：中间结果大时内存吃不消。
  3. Vectorized / Batch Model：
     • 每个 next() 返回一批数据（如 1024 行）。
     • 优点：摊销了函数调用开销，且利于 CPU SIMD 指令优化。
     • 适用：OLAP 系统 (Snowflake, DuckDB, ClickHouse)。
• 执行方向：
  • Top-Down (Pull)：父节点拉取数据（最常见）。
  • Bottom-Up (Push)：子节点将数据推给父节点（利于代码生成和缓存局部性，DuckDB/Hyper 使用）。

3. 易混点或易错点提示#

• ⚠️ Halloween Problem：更新操作改变了元组的物理位置（例如更新了索引键），导致扫描算子重复读到（并重复更新）同一行数据。必须记录已修改的元组 ID 来避免。
• ⚠️ 表达式求值：WHERE 子句通常被解析为表达式树。解释执行（Interpreter）很慢，现代系统使用 JIT 编译 (LLVM) 将表达式树编译成机器码以加速。

4. 简短复习小结#

这一章是将积木搭起来。OLTP 系统多用迭代器模型；OLAP 系统多用向量化模型。无论哪种模型，减少函数调用和利用 CPU 缓存/SIMD 都是优化的关键。

1. 核心概念解释#

• 并行数据库：假设节点间紧密连接（共享内存/磁盘），通信极快且可靠。
• 进程模型 (Process Models)：
  • Process per Worker：每个 Worker 是独立 OS 进程（如 Postgres）。依赖 OS 调度，容错性好，但上下文切换开销大。
  • Thread per Worker：单一进程内多线程（如 MySQL, Oracle, DuckDB）。共享地址空间，通信快，是现代主流选择。

2. 关键结论 / 公式 / 方法#

• 并行的类型：
  • Inter-Query (查询间)：同时执行不同的查询。提高吞吐量，扩展容易。
  • Intra-Query (查询内)：将一个查询拆分给多个 Worker 执行。
    • Intra-Operator (水平并行)：最常见。将数据分区（Partitioning），多个 Worker 运行同一个算子处理不同数据块。需要 Exchange (Barrier) 算子来合并结果。
    • Inter-Operator (垂直并行)：流水线式并行。Worker 1 做 Join，产出结果直接给 Worker 2 做 Projection。较少见，用于流处理。
• I/O 并行：
  • RAID 0 (Striping)：数据跨磁盘切分，读写极快，但坏盘即丢数据。
  • RAID 1 (Mirroring)：数据镜像备份，读快（多点读），写慢（多点写），安全。

3. 易混点或易错点提示#

• ⚠️ Exchange Operator：这不仅仅是数据传输，它充当了路障 (Barrier)。例如在 Hash Join 中，Build 阶段的所有 Worker 必须完成后，Probe 阶段才能开始，以防止数据错误。
• ⚠️ 调度权：数据库绝不应依赖操作系统来调度查询任务，因为操作系统不懂数据依赖和查询代价，数据库自己调度（用户态调度）更高效。

4. 简短复习小结#

并行执行是现代数据库利用多核 CPU 的关键。主流做法是“线程级并行”配合“水平数据分区”。I/O 并行通过 RAID 或分区存储解决磁盘瓶颈。

寄语： 预习时，重点关注为什么要引入这些算法（通常是因为内存放不下）。 复习时，重点对比不同算法的优缺点（如 Hash Join vs. Sort-Merge Join）以及不同处理模型适用的场景（OLTP vs. OLAP）。 祝考试顺利！